<!DOCTYPE html>
<html lang="en-US">
  <head>
    <meta charset="utf-8" />
    <meta name="viewport" content="width=device-width,initial-scale=1" />
    <title>91.leetcode91题.md | aiyoudiao</title>
    <meta name="generator" content="VuePress 1.9.10" />
    <link rel="icon" href="/img/blog.ico">
    <script src="https://cdn.jsdelivr.net/npm/live2d-widget@3.1.4/lib/L2Dwidget.min.js"></script> <meta name="description" content="码二~">
    <meta name="keywords" content="前端博客,个人技术博客,前端,前端开发,前端框架,web前端,前端面试题,技术文档,学习,面试,JavaScript,js,ES6,TypeScript,vue,python,css3,html5,Node,git,github,gitee,markdown">
    <meta name="theme-color" content="#11a8cd">
    <meta name="viewport" content="width=device-width, initial-scale=1.0, minimum-scale=1.0, maximum-scale=1.0, user-scalable=no"> <link rel="preload" href="/assets/css/0.styles.146197cf.css" as="style"><link rel="preload" href="/assets/js/app.bd2fbc77.js" as="script"><link rel="preload" href="/assets/js/3.72c9c947.js" as="script"><link rel="preload" href="/assets/js/130.53e4f9c6.js" as="script"><link rel="preload" href="/assets/js/42.4251ca36.js" as="script"><link rel="prefetch" href="/assets/js/1.4ed4671d.js"><link rel="prefetch" href="/assets/js/10.bd6ddb58.js"><link rel="prefetch" href="/assets/js/100.20d2348f.js"><link rel="prefetch" href="/assets/js/101.ba7b784c.js"><link rel="prefetch" href="/assets/js/102.c3e2dcae.js"><link rel="prefetch" href="/assets/js/103.0f4c50f3.js"><link rel="prefetch" href="/assets/js/104.ef47a111.js"><link rel="prefetch" href="/assets/js/105.2e00f516.js"><link rel="prefetch" href="/assets/js/106.b50e19b9.js"><link rel="prefetch" href="/assets/js/107.e125a8f6.js"><link rel="prefetch" href="/assets/js/108.770493ab.js"><link rel="prefetch" href="/assets/js/109.74766d7b.js"><link rel="prefetch" href="/assets/js/11.f786a5ee.js"><link rel="prefetch" href="/assets/js/110.0b0ee5b4.js"><link rel="prefetch" href="/assets/js/111.835b0e44.js"><link rel="prefetch" href="/assets/js/112.352fa217.js"><link rel="prefetch" href="/assets/js/113.4e908557.js"><link rel="prefetch" href="/assets/js/114.7b77996d.js"><link rel="prefetch" href="/assets/js/115.bdc61268.js"><link rel="prefetch" href="/assets/js/116.d5da9b8b.js"><link rel="prefetch" href="/assets/js/117.35ab1f9f.js"><link rel="prefetch" href="/assets/js/118.517c151d.js"><link rel="prefetch" href="/assets/js/119.f7f49ba8.js"><link rel="prefetch" href="/assets/js/12.3c729a65.js"><link rel="prefetch" href="/assets/js/120.b559598b.js"><link rel="prefetch" href="/assets/js/121.bf8a2f43.js"><link rel="prefetch" href="/assets/js/122.11a0bc97.js"><link rel="prefetch" href="/assets/js/123.2bafdde7.js"><link rel="prefetch" href="/assets/js/124.dc393688.js"><link rel="prefetch" href="/assets/js/125.ed3f389a.js"><link rel="prefetch" href="/assets/js/126.8fd9a57d.js"><link rel="prefetch" href="/assets/js/127.3bf2a1f2.js"><link rel="prefetch" href="/assets/js/128.b9c671d3.js"><link rel="prefetch" href="/assets/js/129.5d331f0d.js"><link rel="prefetch" href="/assets/js/13.7b1a1fe5.js"><link rel="prefetch" href="/assets/js/131.dcc47e1d.js"><link rel="prefetch" href="/assets/js/132.692dcdcd.js"><link rel="prefetch" href="/assets/js/133.e293202c.js"><link rel="prefetch" href="/assets/js/134.593dccf2.js"><link rel="prefetch" href="/assets/js/135.d76d384b.js"><link rel="prefetch" href="/assets/js/136.a519c23c.js"><link rel="prefetch" href="/assets/js/137.b1821288.js"><link rel="prefetch" href="/assets/js/138.5bcea4ef.js"><link rel="prefetch" href="/assets/js/139.076664b0.js"><link rel="prefetch" href="/assets/js/14.35f257b2.js"><link rel="prefetch" href="/assets/js/140.a019e655.js"><link rel="prefetch" href="/assets/js/141.1f70e1c7.js"><link rel="prefetch" href="/assets/js/142.5ed728fd.js"><link rel="prefetch" href="/assets/js/143.1c8cdc78.js"><link rel="prefetch" href="/assets/js/144.b0cb125b.js"><link rel="prefetch" href="/assets/js/145.c0209a76.js"><link rel="prefetch" href="/assets/js/146.551469f4.js"><link rel="prefetch" href="/assets/js/147.1dfd721d.js"><link rel="prefetch" href="/assets/js/148.91d07ef5.js"><link rel="prefetch" href="/assets/js/149.5b88b710.js"><link rel="prefetch" href="/assets/js/15.23bbc29a.js"><link rel="prefetch" href="/assets/js/150.8301107f.js"><link rel="prefetch" href="/assets/js/151.867da089.js"><link rel="prefetch" href="/assets/js/152.935d5046.js"><link rel="prefetch" href="/assets/js/153.f39d8435.js"><link rel="prefetch" href="/assets/js/154.6b9eb2c3.js"><link rel="prefetch" href="/assets/js/155.14283ad4.js"><link rel="prefetch" href="/assets/js/156.2d7c1a2a.js"><link rel="prefetch" href="/assets/js/157.2f28d02f.js"><link rel="prefetch" href="/assets/js/158.151221ae.js"><link rel="prefetch" href="/assets/js/159.ef6d7ffe.js"><link rel="prefetch" href="/assets/js/16.1793aef7.js"><link rel="prefetch" href="/assets/js/160.de54c4ea.js"><link rel="prefetch" href="/assets/js/161.24d4e57c.js"><link rel="prefetch" href="/assets/js/162.632032fe.js"><link rel="prefetch" href="/assets/js/163.fd01cd99.js"><link rel="prefetch" href="/assets/js/164.45f203f5.js"><link rel="prefetch" href="/assets/js/165.aafe4fe1.js"><link rel="prefetch" href="/assets/js/166.1dd1d21c.js"><link rel="prefetch" href="/assets/js/167.5501b3a1.js"><link rel="prefetch" href="/assets/js/168.fbe58b1f.js"><link rel="prefetch" href="/assets/js/169.2cae7f5e.js"><link rel="prefetch" href="/assets/js/17.bbfe63f2.js"><link rel="prefetch" href="/assets/js/170.265f7c9e.js"><link rel="prefetch" href="/assets/js/171.b61f327d.js"><link rel="prefetch" href="/assets/js/172.5d0043fd.js"><link rel="prefetch" href="/assets/js/173.45284bb6.js"><link rel="prefetch" href="/assets/js/174.9130e0c4.js"><link rel="prefetch" href="/assets/js/175.2b38bddd.js"><link rel="prefetch" href="/assets/js/176.9772cf09.js"><link rel="prefetch" href="/assets/js/177.69048ebc.js"><link rel="prefetch" href="/assets/js/178.e10d7ce5.js"><link rel="prefetch" href="/assets/js/179.3789edc0.js"><link rel="prefetch" href="/assets/js/18.0807ded0.js"><link rel="prefetch" href="/assets/js/180.ab675e47.js"><link rel="prefetch" href="/assets/js/181.2e39eff0.js"><link rel="prefetch" href="/assets/js/19.becf5a76.js"><link rel="prefetch" href="/assets/js/2.eb089a4f.js"><link rel="prefetch" href="/assets/js/20.cea59652.js"><link rel="prefetch" href="/assets/js/21.58c43ff1.js"><link rel="prefetch" href="/assets/js/22.f73b825d.js"><link rel="prefetch" href="/assets/js/23.43b13730.js"><link rel="prefetch" href="/assets/js/24.f77f93ca.js"><link rel="prefetch" href="/assets/js/25.7dfaf3fb.js"><link rel="prefetch" href="/assets/js/26.629d28e5.js"><link rel="prefetch" href="/assets/js/27.4fff23ea.js"><link rel="prefetch" href="/assets/js/28.1b8ae389.js"><link rel="prefetch" href="/assets/js/29.d5cce9a0.js"><link rel="prefetch" href="/assets/js/30.961d5519.js"><link rel="prefetch" href="/assets/js/31.121dd1af.js"><link rel="prefetch" href="/assets/js/32.4a3c5df7.js"><link rel="prefetch" href="/assets/js/33.5537f44b.js"><link rel="prefetch" href="/assets/js/34.1d4d4653.js"><link rel="prefetch" href="/assets/js/35.d094209b.js"><link rel="prefetch" href="/assets/js/36.832660c5.js"><link rel="prefetch" href="/assets/js/37.145c3665.js"><link rel="prefetch" href="/assets/js/38.4f369bfe.js"><link rel="prefetch" href="/assets/js/39.ba060044.js"><link rel="prefetch" href="/assets/js/4.66d742f6.js"><link rel="prefetch" href="/assets/js/40.e50e0379.js"><link rel="prefetch" href="/assets/js/41.4ed7617c.js"><link rel="prefetch" href="/assets/js/43.d22b74c4.js"><link rel="prefetch" href="/assets/js/44.59439f9d.js"><link rel="prefetch" href="/assets/js/45.da28bc46.js"><link rel="prefetch" href="/assets/js/46.b8db1176.js"><link rel="prefetch" href="/assets/js/47.7ed16fc7.js"><link rel="prefetch" href="/assets/js/48.c982d5ed.js"><link rel="prefetch" href="/assets/js/49.a7579f55.js"><link rel="prefetch" href="/assets/js/5.08802d7d.js"><link rel="prefetch" href="/assets/js/50.103b5bf6.js"><link rel="prefetch" href="/assets/js/51.0fe9d79a.js"><link rel="prefetch" href="/assets/js/52.9ba31e26.js"><link rel="prefetch" href="/assets/js/53.0e8bc1f0.js"><link rel="prefetch" href="/assets/js/54.9566e517.js"><link rel="prefetch" href="/assets/js/55.a124abae.js"><link rel="prefetch" href="/assets/js/56.d9cf0800.js"><link rel="prefetch" href="/assets/js/57.93599da0.js"><link rel="prefetch" href="/assets/js/58.d943f85b.js"><link rel="prefetch" href="/assets/js/59.50a66488.js"><link rel="prefetch" href="/assets/js/6.a3ea60eb.js"><link rel="prefetch" href="/assets/js/60.21aa3aa3.js"><link rel="prefetch" href="/assets/js/61.6712c00f.js"><link rel="prefetch" href="/assets/js/62.eff3e4b1.js"><link rel="prefetch" href="/assets/js/63.09701d5a.js"><link rel="prefetch" href="/assets/js/64.eb440dec.js"><link rel="prefetch" href="/assets/js/65.aeed0579.js"><link rel="prefetch" href="/assets/js/66.97244c64.js"><link rel="prefetch" href="/assets/js/67.e01c5c24.js"><link rel="prefetch" href="/assets/js/68.21be91ba.js"><link rel="prefetch" href="/assets/js/69.c0849905.js"><link rel="prefetch" href="/assets/js/7.7fd40e91.js"><link rel="prefetch" href="/assets/js/70.b32bbe5d.js"><link rel="prefetch" href="/assets/js/71.0efbc0c7.js"><link rel="prefetch" href="/assets/js/72.ef963181.js"><link rel="prefetch" href="/assets/js/73.ca7dd5db.js"><link rel="prefetch" href="/assets/js/74.4483ede8.js"><link rel="prefetch" href="/assets/js/75.374ab483.js"><link rel="prefetch" href="/assets/js/76.b4a39f08.js"><link rel="prefetch" href="/assets/js/77.6b30c3cd.js"><link rel="prefetch" href="/assets/js/78.15376c33.js"><link rel="prefetch" href="/assets/js/79.3153fcec.js"><link rel="prefetch" href="/assets/js/80.9a88c684.js"><link rel="prefetch" href="/assets/js/81.1e3f842c.js"><link rel="prefetch" href="/assets/js/82.996dbd3d.js"><link rel="prefetch" href="/assets/js/83.955158bf.js"><link rel="prefetch" href="/assets/js/84.71bdc76d.js"><link rel="prefetch" href="/assets/js/85.774e49f2.js"><link rel="prefetch" href="/assets/js/86.bebf32e5.js"><link rel="prefetch" href="/assets/js/87.becdbde1.js"><link rel="prefetch" href="/assets/js/88.49e933f4.js"><link rel="prefetch" href="/assets/js/89.eeceedfd.js"><link rel="prefetch" href="/assets/js/90.3ea6dd12.js"><link rel="prefetch" href="/assets/js/91.62a6a556.js"><link rel="prefetch" href="/assets/js/92.e2ebb8f5.js"><link rel="prefetch" href="/assets/js/93.dcdefe7a.js"><link rel="prefetch" href="/assets/js/94.bf412146.js"><link rel="prefetch" href="/assets/js/95.8deadcdc.js"><link rel="prefetch" href="/assets/js/96.9977087a.js"><link rel="prefetch" href="/assets/js/97.6591f9da.js"><link rel="prefetch" href="/assets/js/98.4db7f75e.js"><link rel="prefetch" href="/assets/js/99.a61462e9.js"><link rel="prefetch" href="/assets/js/vendors~docsearch.2852b102.js"> <link rel="stylesheet" href="/assets/css/0.styles.146197cf.css">
  </head>
  <body class="theme-mode-light">
    <div id="app" data-server-rendered="true"><div class="theme-container sidebar-open have-rightmenu"><header class="navbar blur"><div title="目录" class="sidebar-button"><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" width="50" height="50" class="icon"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path></svg></div> <a href="/" class="home-link router-link-active"><img src="https://p3-passport.byteacctimg.com/img/user-avatar/794fdae4ff249d532da19a3c26d420ed~300x300.image" alt="aiyoudiao" class="logo"> <span class="site-name can-hide">
      aiyoudiao
    </span></a> <div class="links"><div class="sky-switch" data-v-3a03d589><label for="toggle" data-v-3a03d589><input id="toggle" type="checkbox" data-v-3a03d589><div data-v-3a03d589></div></label></div> <div class="search-box"><input aria-label="Search" autocomplete="off" spellcheck="false" value=""> <!----></div> <nav class="nav-links can-hide"><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="笔记" class="dropdown-title"><!----> <span class="title" style="display:;">笔记</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/pages/84633490449/" class="nav-link">
  JavaScript
</a></li><li class="dropdown-item"><!----> <a href="/pages/2331001041/" class="nav-link">
  Vue
</a></li><li class="dropdown-item"><!----> <a href="/pages/18114480448/" class="nav-link">
  React
</a></li><li class="dropdown-item"><!----> <a href="/pages/25236260426/" class="nav-link">
  低代码
</a></li><li class="dropdown-item"><!----> <a href="/pages/35345230523/" class="nav-link">
  线性系统
</a></li><li class="dropdown-item"><!----> <a href="/pages/08313561056/" class="nav-link">
  暂未分类
</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="算法与设计" class="dropdown-title"><!----> <span class="title" style="display:;">算法与设计</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/pages/70741550255/" class="nav-link">
  LeetCode
</a></li><li class="dropdown-item"><!----> <a href="/pages/17845450445/" class="nav-link">
  算法
</a></li><li class="dropdown-item"><!----> <a href="/pages/90132170217/" class="nav-link">
  数据结构
</a></li><li class="dropdown-item"><!----> <a href="/pages/50546120212/" class="nav-link">
  设计模式
</a></li><li class="dropdown-item"><!----> <a href="/pages/02344550255/" class="nav-link">
  Other
</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="技能" class="dropdown-title"><!----> <span class="title" style="display:;">技能</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/pages/82158160216/" class="nav-link">
  PMP
</a></li><li class="dropdown-item"><!----> <a href="/pages/41858590259/" class="nav-link">
  Office
</a></li><li class="dropdown-item"><!----> <a href="/pages/02359360236/" class="nav-link">
  面试
</a></li><li class="dropdown-item"><!----> <a href="/pages/73600130213/" class="nav-link">
  Bash
</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="历程" class="dropdown-title"><!----> <span class="title" style="display:;">历程</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/pages/83857320232/" class="nav-link">
  流年往事
</a></li><li class="dropdown-item"><!----> <a href="/pages/93419130213/" class="nav-link">
  经验片段
</a></li><li class="dropdown-item"><!----> <a href="/pages/99744220322/" class="nav-link">
  读书杂感
</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="首页" class="dropdown-title"><!----> <span class="title" style="display:;">首页</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/archives/" class="nav-link">
  归档
</a></li><li class="dropdown-item"><!----> <a href="/categories/" class="nav-link">
  分类
</a></li><li class="dropdown-item"><!----> <a href="/tags/" class="nav-link">
  标签
</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="其它" class="dropdown-title"><!----> <span class="title" style="display:;">其它</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/pages/02657130213/" class="nav-link">
  简介
</a></li><li class="dropdown-item"><!----> <a href="/pages/5390102042/" class="nav-link">
  收藏
</a></li><li class="dropdown-item"><!----> <a href="/pages/32309510451/" class="nav-link">
  有趣
</a></li><li class="dropdown-item"><!----> <a href="/pages/23313210521/" class="nav-link">
  文档
</a></li></ul></div></div> <!----></nav></div></header> <div class="sidebar-mask"></div> <div class="sidebar-hover-trigger"></div> <aside class="sidebar" style="display:none;"><div class="blogger"><img src="/img/mar.jpg"> <div class="blogger-info"><h3>码二</h3> <span>扫微信二维码，认识一下码二吧😉。</span></div></div> <nav class="nav-links"><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="笔记" class="dropdown-title"><!----> <span class="title" style="display:;">笔记</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/pages/84633490449/" class="nav-link">
  JavaScript
</a></li><li class="dropdown-item"><!----> <a href="/pages/2331001041/" class="nav-link">
  Vue
</a></li><li class="dropdown-item"><!----> <a href="/pages/18114480448/" class="nav-link">
  React
</a></li><li class="dropdown-item"><!----> <a href="/pages/25236260426/" class="nav-link">
  低代码
</a></li><li class="dropdown-item"><!----> <a href="/pages/35345230523/" class="nav-link">
  线性系统
</a></li><li class="dropdown-item"><!----> <a href="/pages/08313561056/" class="nav-link">
  暂未分类
</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="算法与设计" class="dropdown-title"><!----> <span class="title" style="display:;">算法与设计</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/pages/70741550255/" class="nav-link">
  LeetCode
</a></li><li class="dropdown-item"><!----> <a href="/pages/17845450445/" class="nav-link">
  算法
</a></li><li class="dropdown-item"><!----> <a href="/pages/90132170217/" class="nav-link">
  数据结构
</a></li><li class="dropdown-item"><!----> <a href="/pages/50546120212/" class="nav-link">
  设计模式
</a></li><li class="dropdown-item"><!----> <a href="/pages/02344550255/" class="nav-link">
  Other
</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="技能" class="dropdown-title"><!----> <span class="title" style="display:;">技能</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/pages/82158160216/" class="nav-link">
  PMP
</a></li><li class="dropdown-item"><!----> <a href="/pages/41858590259/" class="nav-link">
  Office
</a></li><li class="dropdown-item"><!----> <a href="/pages/02359360236/" class="nav-link">
  面试
</a></li><li class="dropdown-item"><!----> <a href="/pages/73600130213/" class="nav-link">
  Bash
</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="历程" class="dropdown-title"><!----> <span class="title" style="display:;">历程</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/pages/83857320232/" class="nav-link">
  流年往事
</a></li><li class="dropdown-item"><!----> <a href="/pages/93419130213/" class="nav-link">
  经验片段
</a></li><li class="dropdown-item"><!----> <a href="/pages/99744220322/" class="nav-link">
  读书杂感
</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="首页" class="dropdown-title"><!----> <span class="title" style="display:;">首页</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/archives/" class="nav-link">
  归档
</a></li><li class="dropdown-item"><!----> <a href="/categories/" class="nav-link">
  分类
</a></li><li class="dropdown-item"><!----> <a href="/tags/" class="nav-link">
  标签
</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="其它" class="dropdown-title"><!----> <span class="title" style="display:;">其它</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/pages/02657130213/" class="nav-link">
  简介
</a></li><li class="dropdown-item"><!----> <a href="/pages/5390102042/" class="nav-link">
  收藏
</a></li><li class="dropdown-item"><!----> <a href="/pages/32309510451/" class="nav-link">
  有趣
</a></li><li class="dropdown-item"><!----> <a href="/pages/23313210521/" class="nav-link">
  文档
</a></li></ul></div></div> <!----></nav>  <ul class="sidebar-links"><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading open"><span>LeetCode</span> <span class="arrow down"></span></p> <ul class="sidebar-links sidebar-group-items"><li><a href="/pages/7221208038/" class="sidebar-link">剑指 Offer 10- I_斐波那契数列</a></li><li><a href="/pages/70741550255/" class="sidebar-link">第1题-两数之和</a></li><li><a href="/pages/79952361036/" aria-current="page" class="active sidebar-link">leetcode91题</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/pages/79952361036/#前言" class="sidebar-link">前言</a></li><li class="sidebar-sub-header"><a href="/pages/79952361036/#leetcode-91题-解码方法" class="sidebar-link">leetcode 91题 解码方法</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/pages/79952361036/#题目" class="sidebar-link">题目</a></li><li class="sidebar-sub-header"><a href="/pages/79952361036/#要求" class="sidebar-link">要求</a></li><li class="sidebar-sub-header"><a href="/pages/79952361036/#分析" class="sidebar-link">分析</a></li></ul></li><li class="sidebar-sub-header"><a href="/pages/79952361036/#核心扩展" class="sidebar-link">核心扩展</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/pages/79952361036/#求斐波那契数列-递归的暴力解法" class="sidebar-link">求斐波那契数列（递归的暴力解法）</a></li><li class="sidebar-sub-header"><a href="/pages/79952361036/#求斐波那契数列-带备忘录的递归解法" class="sidebar-link">求斐波那契数列 （带备忘录的递归解法）</a></li><li class="sidebar-sub-header"><a href="/pages/79952361036/#求斐波那契数列-非递归的动态规划解法" class="sidebar-link">求斐波那契数列 （非递归的动态规划解法）</a></li></ul></li><li class="sidebar-sub-header"><a href="/pages/79952361036/#动态规划" class="sidebar-link">动态规划</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/pages/79952361036/#leetcode-322题-零钱兑换" class="sidebar-link">leetcode 322题 零钱兑换</a></li><li class="sidebar-sub-header"><a href="/pages/79952361036/#要求-2" class="sidebar-link">要求</a></li><li class="sidebar-sub-header"><a href="/pages/79952361036/#分析-2" class="sidebar-link">分析</a></li></ul></li><li class="sidebar-sub-header"><a href="/pages/79952361036/#另类题解" class="sidebar-link">另类题解</a></li></ul></li></ul></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>算法</span> <span class="arrow right"></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>数据结构</span> <span class="arrow right"></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>设计模式</span> <span class="arrow right"></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>Other</span> <span class="arrow right"></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>vue3设计与实现</span> <span class="arrow right"></span></p> <!----></section></li></ul> </aside> <div><main class="page"> <div class="theme-vdoing-wrapper bg-style-1"><div class="articleInfo-wrap" data-v-18fb2c02><div class="articleInfo" data-v-18fb2c02><ul class="breadcrumbs" data-v-18fb2c02><li data-v-18fb2c02><a href="/" title="首页" class="iconfont icon-home router-link-active" data-v-18fb2c02></a></li> <li data-v-18fb2c02><a href="/categories/?category=%E7%AE%97%E6%B3%95%E4%B8%8E%E8%AE%BE%E8%AE%A1" title="分类" data-v-18fb2c02>
          算法与设计
        </a></li> <li data-v-18fb2c02><a href="/categories/?category=LeetCode" title="分类" data-v-18fb2c02>
          LeetCode
        </a></li> <!----></ul> <div class="info" data-v-18fb2c02><div title="作者" class="author iconfont icon-touxiang" data-v-18fb2c02><a href="javascript:;" data-v-18fb2c02>aiyoudiao</a></div> <div title="创建时间" class="date iconfont icon-riqi" data-v-18fb2c02><a href="javascript:;" data-v-18fb2c02>2022-10-16</a></div> <!----></div></div></div> <!----> <div class="content-wrapper"><div class="right-menu-wrapper"><div class="right-menu-margin"><div class="right-menu-content"></div></div></div> <h1><!----> <span>
            91.leetcode91题.md
          </span></h1> <div class="theme-vdoing-content content__default"><h2 id="前言"><a href="#前言" class="header-anchor">#</a> 前言</h2> <p>91题<strong>解码方法</strong>的难度属于中等，但其涉及到的知识并不少呢，斐波那契、备忘录剪枝、动态规划等等，除了题解之外，我也会深入浅出的讲解这些知识点，文章末尾我还会使用 正则 + 斐波那契的写法来解题，我们一起来看看。</p> <h2 id="leetcode-91题-解码方法"><a href="#leetcode-91题-解码方法" class="header-anchor">#</a> leetcode 91题 解码方法</h2> <p>题目地址：https://leetcode-cn.com/problems/decode-ways/</p> <h3 id="题目"><a href="#题目" class="header-anchor">#</a> 题目</h3> <p>一条包含字母 <code>A-Z</code> 的消息通过以下映射进行了 <code>编码</code> ：</p> <div class="language- extra-class"><pre class="language-text"><code>'A' -&gt; 1
'B' -&gt; 2
...
'Z' -&gt; 26
</code></pre></div><p>要 <code>解码</code> 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，<code>&quot;11106&quot;</code> 可以映射为：</p> <ul><li><code>&quot;AAJF&quot;</code> ，将消息分组为 <code>(1 1 10 6)</code></li> <li><code>&quot;KJF&quot;</code> ，将消息分组为 <code>(11 10 6)</code></li></ul> <p>注意，消息不能分组为  <code>(1 11 06)</code> ，因为 <code>&quot;06&quot;</code> 不能映射为 <code>&quot;F&quot;</code> ，这是由于 <code>&quot;6&quot;</code> 和 <code>&quot;06&quot;</code> 在映射中并不等价。</p> <p>给你一个只含数字的 <code>非空</code> 字符串 <code>s</code> ，请计算并返回 <code>解码</code> 方法的 <code>总数</code>。</p> <p>题目数据保证答案肯定是一个 <code>32 位</code>  的整数。</p> <p><strong>示例 1：</strong></p> <div class="language- extra-class"><pre class="language-text"><code>输入： s = &quot;12&quot;
输出： 2
解释： 它可以解码为 &quot;AB&quot;（1 2）或者 &quot;L&quot;（12）。
</code></pre></div><p><strong>示例 2：</strong></p> <div class="language- extra-class"><pre class="language-text"><code>输入： s = &quot;226&quot;
输出： 3
解释： 它可以解码为 &quot;BZ&quot; (2 26), &quot;VF&quot; (22 6), 或者 &quot;BBF&quot; (2 2 6) 。
</code></pre></div><p><strong>示例 3：</strong></p> <div class="language- extra-class"><pre class="language-text"><code>输入： s = &quot;0&quot;
输出： 0
解释： 没有字符映射到以 0 开头的数字。
含有 0 的有效映射是 'J' -&gt; &quot;10&quot; 和 'T'-&gt; &quot;20&quot; 。
由于没有字符，因此没有有效的方法对此进行解码，因为所有数字都需要映射。
</code></pre></div><p><strong>示例 4：</strong></p> <div class="language- extra-class"><pre class="language-text"><code>输入： s = &quot;06&quot;
输出： 0
解释： &quot;06&quot; 不能映射到 &quot;F&quot; ，因为字符串含有前导 0（`&quot;6&quot;` 和 `&quot;06&quot;` 在映射中并不等价）。
</code></pre></div><p><strong>提示：</strong></p> <ul><li><code>1 &lt;= s.length &lt;= 100</code></li> <li><code>s</code> 只包含数字，并且可能包含前导零。</li></ul> <h3 id="要求"><a href="#要求" class="header-anchor">#</a> 要求</h3> <ul><li>统计能解码(匹配)到的个数。</li> <li>0 开头的数字不行。</li> <li>映射的结果在26个字母范围之内。</li> <li>这是一个斐波那契规律的字符串。</li></ul> <h3 id="分析"><a href="#分析" class="header-anchor">#</a> 分析</h3> <p>开头为 0 直接返回 0。</p> <p>0 是一个特殊的判断条件。</p> <p>每一个匹配到的值必须小于等于26。</p> <p>这是一个符合斐波那契数列规律的问题。</p> <div class="language-js extra-class"><pre class="language-js"><code><span class="token keyword">var</span> <span class="token function-variable function">numDecodings</span> <span class="token operator">=</span> <span class="token keyword">function</span> <span class="token punctuation">(</span><span class="token parameter">s</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
  <span class="token keyword">const</span> n <span class="token operator">=</span> s<span class="token punctuation">.</span>length<span class="token punctuation">;</span>
  <span class="token comment">// 如果 n === 0 或者 s[0] === '0'，直接结束，我喜欢使用includes</span>
  <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token function">isZero</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span> <span class="token operator">||</span> <span class="token function">isZero</span><span class="token punctuation">(</span>s<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">return</span> <span class="token number">0</span>
  <span class="token punctuation">}</span>
  
  <span class="token comment">// 使用一个表来存取匹配到的数量</span>
  <span class="token keyword">const</span> dpTable <span class="token operator">=</span> <span class="token function">Array</span><span class="token punctuation">(</span>n <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">.</span><span class="token function">fill</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">)</span>
  <span class="token comment">// 斐波那契</span>
  dpTable<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">1</span>
  dpTable<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">1</span>
  
  <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">let</span> i <span class="token operator">=</span> <span class="token number">2</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> n<span class="token punctuation">;</span> i <span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token comment">// 情况一：倒数一位不为0</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token operator">!</span><span class="token function">isZero</span><span class="token punctuation">(</span>s<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
      dpTable<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> dpTable<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">+</span> dpTable<span class="token punctuation">[</span>i <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    
    <span class="token comment">// 情况二：倒数两位 大于等于 10 并且小于等于 26</span>
    <span class="token keyword">const</span> value <span class="token operator">=</span><span class="token function">Number</span><span class="token punctuation">(</span>dpTable<span class="token punctuation">[</span>i <span class="token operator">-</span> <span class="token number">2</span><span class="token punctuation">]</span> <span class="token operator">+</span> dpTable<span class="token punctuation">[</span>i <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>value <span class="token operator">&gt;=</span> <span class="token number">10</span> <span class="token operator">&amp;&amp;</span> value  <span class="token operator">&lt;=</span> <span class="token number">26</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
      dpTable<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> dpTable<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">+</span> dpTable<span class="token punctuation">[</span>i <span class="token operator">-</span> <span class="token number">2</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
  <span class="token punctuation">}</span>
  
  <span class="token keyword">return</span> dpTable<span class="token punctuation">[</span>n<span class="token punctuation">]</span>
  
  <span class="token keyword">function</span> <span class="token function">isZero</span><span class="token punctuation">(</span><span class="token parameter">num</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">return</span> <span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">,</span> <span class="token string">'0'</span><span class="token punctuation">]</span><span class="token punctuation">.</span><span class="token function">includes</span><span class="token punctuation">(</span>num<span class="token punctuation">)</span>
  <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre></div><h2 id="核心扩展"><a href="#核心扩展" class="header-anchor">#</a> 核心扩展</h2> <p>91题的题解使用到了动态规划，动态规划是很常见的算法设计技巧，同时这道题也使用到了斐波那契数列的规律，那我们就那斐波那契数列来举例吧。</p> <p>层层递进的固定流程：递归的暴力解法 -&gt; 带备忘录的递归解法 -&gt; 非递归的动态规划解法</p> <h3 id="求斐波那契数列-递归的暴力解法"><a href="#求斐波那契数列-递归的暴力解法" class="header-anchor">#</a> 求斐波那契数列（递归的暴力解法）</h3> <div class="language-js extra-class"><pre class="language-js"><code><span class="token keyword">function</span> <span class="token function">fibonacci</span> <span class="token punctuation">(</span><span class="token parameter">n</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
  <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">]</span><span class="token punctuation">.</span><span class="token function">includes</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">return</span> <span class="token number">1</span>
  <span class="token punctuation">}</span>
  
  <span class="token keyword">return</span> <span class="token function">fibonacci</span><span class="token punctuation">(</span>n <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">+</span> <span class="token function">fibonacci</span><span class="token punctuation">(</span>n <span class="token operator">-</span> <span class="token number">2</span><span class="token punctuation">)</span>
<span class="token punctuation">}</span>
</code></pre></div><p>把这种暴力递归的解法画一张图出来：
<img src="https://cdn.jsdelivr.net/gh/filess/img12@main/2021/05/28/1622181356687-00195145-9756-402d-930f-75e3ccefc4c3.png" alt=""></p> <p>是不是有重复的计算？像这样的二叉树的节点总数是指数级的，所以所有子问题的个数为 (n^2) 噢，这么做会导致时间复杂度爆炸，因为时间复杂度也变成了 O(n^2) 。</p> <h3 id="求斐波那契数列-带备忘录的递归解法"><a href="#求斐波那契数列-带备忘录的递归解法" class="header-anchor">#</a> 求斐波那契数列 （带备忘录的递归解法）</h3> <div class="language-js extra-class"><pre class="language-js"><code><span class="token keyword">let</span> dp <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">]</span>
<span class="token keyword">function</span> <span class="token function">fibonacci</span> <span class="token punctuation">(</span><span class="token parameter">n</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
  <span class="token keyword">if</span> <span class="token punctuation">(</span>dp<span class="token punctuation">[</span>n <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">return</span> dp<span class="token punctuation">[</span>n <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span>
  <span class="token punctuation">}</span>
  
  dp<span class="token punctuation">[</span>n <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token function">fibonacci</span><span class="token punctuation">(</span>n <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">+</span> <span class="token function">fibonacci</span><span class="token punctuation">(</span>n <span class="token operator">-</span> <span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token keyword">return</span> dp<span class="token punctuation">[</span>n <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span>
<span class="token punctuation">}</span>
</code></pre></div><p>这种带备忘录的递归解法是针对暴力递归的解法做的优化，优化的操作其实就是对那颗指数级的二叉树进行剪枝，剪枝会减少重复的树节点(减少了重复的计算)。</p> <p>这种带备忘录的递归解法也画一张图出来：</p> <p><img src="https://cdn.jsdelivr.net/gh/filess/img4@main/2021/05/28/1622183223674-db365356-54b6-4cc7-98db-1fda3aa3451f.png" alt=""></p> <p>红色实线部分圈着的是被剪枝的节点，是不是剪掉了所有的重复树节点？没错是的，所有重复的子问题都被干掉了，时间复杂度骤减。</p> <p>没错，它时间复杂度也从O(n^2)降低到了O(n)，如果用空间去换时间的话，它的时间复杂度甚至还会从O(n) 降 O(1)。</p> <blockquote><p>惊叹算法设计的神奇。从O(n^2)到O(n)再到O(1)，速度一下子就上去了。
假设这个 n 为 1000，O(1000^2)、O(1000)、O(1) 这三者相比之下，可以体会到时间复杂度的提升是<code>质的飞升</code>。</p></blockquote> <h3 id="求斐波那契数列-非递归的动态规划解法"><a href="#求斐波那契数列-非递归的动态规划解法" class="header-anchor">#</a> 求斐波那契数列 （非递归的动态规划解法）</h3> <div class="language-js extra-class"><pre class="language-js"><code><span class="token keyword">function</span> <span class="token function">fibonacci</span> <span class="token punctuation">(</span><span class="token parameter">n</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
  <span class="token keyword">let</span> dp <span class="token operator">=</span> <span class="token function">Array</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span><span class="token punctuation">.</span><span class="token function">fill</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
  dp<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">=</span> dp<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>

  <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">let</span> i <span class="token operator">=</span> <span class="token number">2</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> n<span class="token punctuation">;</span> i <span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> dp<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">+</span> dp<span class="token punctuation">[</span>i <span class="token operator">-</span> <span class="token number">2</span><span class="token punctuation">]</span>
  <span class="token punctuation">}</span>

  <span class="token keyword">return</span> dp<span class="token punctuation">[</span>n <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre></div><p>无论是递归的暴力解法还是带备忘录的递归解法，实际上本质都是自顶向下(从上到下)，看上面两张图不难发现这个规律。</p> <p>使用动态规划的方式，你可以看到我们是自底向上(从下往上)，也就是从最小的问题逐渐往上推，先求fibonacci(2)再求fibonacci(3)...最后fibonacci(20)。</p> <blockquote><p>递归是自顶向下，从上向下的延申，逐层分解问题的规模，直到触及到底部(小问题得以解决)，然后再逐层的向上返回答案，最后求出最大的那个问题的解。
动态规划一般都是非递归的，是自底向上的循环迭代，先解决最小规模的问题，再用小问题的答案求解除最大规模问题的解。</p></blockquote> <h2 id="动态规划"><a href="#动态规划" class="header-anchor">#</a> 动态规划</h2> <p>从求斐波那契数列的非递归动态规划解法中，我可以分析到三个要素，这三个要素也是动态规划的显著特征。</p> <ul><li>状态转移方程：例如 dp[0] = dp[1] = 1;dp[i] = dp[i-1] + dp[i-2];</li> <li>暴力解法：想到了这个状态转移方程后，就能写出这个暴力解的算法，比如使用 DP Table 和 for循环 来实现求斐波那契数列的算法 。</li> <li>独立最优子结构：子问题必须相互独立，最大规模问题的解是由多个子问题的最优解计算得来的。</li></ul> <p>画一下这三个特征的图：</p> <p><img src="https://cdn.jsdelivr.net/gh/filess/img3@main/2021/05/31/1622428301383-d24fd5ee-79ff-4ed6-a6cc-77538a0d1a1f.png" alt=""></p> <p>也许这张图不是很明显，那么可以换另一个更生动的方式来说明，比如leetcode 中 <code>322.零钱兑换</code>。</p> <h3 id="leetcode-322题-零钱兑换"><a href="#leetcode-322题-零钱兑换" class="header-anchor">#</a> leetcode 322题 零钱兑换</h3> <p>给定不同面额的硬币 <code>coins</code> 和一个总金额 <code>amount</code>。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 <code>-1</code>。</p> <p>你可以认为每种硬币的数量是无限的。</p> <p><strong>示例 1：</strong></p> <div class="language- extra-class"><pre class="language-text"><code>输入： coins = [1, 2, 5], amount = 11
输出： 3
解释： 11 = 5 + 5 + 1
</code></pre></div><p><strong>示例 2：</strong></p> <div class="language- extra-class"><pre class="language-text"><code>输入：coins = [2], amount = 3
输出：-1
</code></pre></div><p><strong>示例 3：</strong></p> <div class="language- extra-class"><pre class="language-text"><code>输入： coins = [1], amount = 0
输出： 0
</code></pre></div><p><strong>示例 4：</strong></p> <div class="language- extra-class"><pre class="language-text"><code>输入： coins = [1], amount = 1
输出： 1
</code></pre></div><p><strong>示例 5：</strong></p> <div class="language- extra-class"><pre class="language-text"><code>输入： coins = [1], amount = 2
输出： 2
</code></pre></div><p><strong>提示：</strong></p> <ul><li><code>1 &lt;= coins.length &lt;= 12</code></li> <li><code>1 &lt;= coins[i] &lt;= 231 - 1</code></li> <li><code>0 &lt;= amount &lt;= 104</code></li></ul> <h3 id="要求-2"><a href="#要求-2" class="header-anchor">#</a> 要求</h3> <ul><li>有三种面额的金币：1元、2元、5元</li> <li>用这三种面额的金币组合出指定的总额</li> <li>这三种面额的金币支持重复组合</li> <li>最少使用几枚可以组合出指定的总额</li></ul> <h3 id="分析-2"><a href="#分析-2" class="header-anchor">#</a> 分析</h3> <p>总额为13，那么最少需要四张：5 + 5 + 2 + 1</p> <p>总额为0 时，直接返回 0</p> <p>每一次的解都在 coins中，下一次的因依赖与上一次的解，比如 第一次的解为5，下一次的因就是 13 - 5，那么剩下的解就是 从 8 中计算得出。</p> <p>可以遍历coins，如果下一次的因小于 coins中某个金币面额，那么就continue一下，切换下一个面额。</p> <p>累积计数，求最小值。</p> <p><strong>递归的写法</strong></p> <p>这种写法性能贼差嘞，递归中套循环，循环中有递归，复杂度是 O(n^count)，也就是n的每一轮循环的总次数的那么多次方噢，爆炸，如果coins中有五个元素，那么时间复杂度就是O(n^5)，爆炸了爆炸了。</p> <div class="language-js extra-class"><pre class="language-js"><code><span class="token keyword">var</span> <span class="token function-variable function">coinChange</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token parameter">coins<span class="token punctuation">,</span> amount</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">,</span> <span class="token string">'0'</span><span class="token punctuation">]</span><span class="token punctuation">.</span><span class="token function">includes</span><span class="token punctuation">(</span>amount<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token number">0</span>
    <span class="token punctuation">}</span>

    <span class="token keyword">let</span> temp <span class="token operator">=</span> Number<span class="token punctuation">.</span><span class="token constant">MAX_VALUE</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">let</span> coin <span class="token keyword">of</span> coins<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>amount <span class="token operator">-</span> coin <span class="token operator">&lt;</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token keyword">continue</span><span class="token punctuation">;</span>

        <span class="token keyword">const</span> result <span class="token operator">=</span> <span class="token function">coinChange</span><span class="token punctuation">(</span>coins<span class="token punctuation">,</span> amount <span class="token operator">-</span> coin<span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">if</span> <span class="token punctuation">(</span>result <span class="token operator">===</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span> <span class="token keyword">continue</span><span class="token punctuation">;</span>

        temp <span class="token operator">=</span> Math<span class="token punctuation">.</span><span class="token function">min</span><span class="token punctuation">(</span>temp<span class="token punctuation">,</span> result <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token keyword">return</span> temp <span class="token operator">===</span> Number<span class="token punctuation">.</span><span class="token constant">MAX_VALUE</span> <span class="token operator">?</span> <span class="token operator">-</span><span class="token number">1</span> <span class="token operator">:</span> temp
<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre></div><p>如图：</p> <p><img src="https://cdn.jsdelivr.net/gh/filess/img5@main/2021/05/31/1622444243227-e680adf0-0b2f-4324-b89e-64d5ffaddc2b.png" alt=""></p> <p><strong>带备忘录的递归写法</strong></p> <p>这种写法对原来的递归树进行了剪枝操作，极大的减少了重复的运算。复杂度是O(n*count)，重复的问题都不会继续运算，时间复杂度是O(n)。</p> <div class="language-js extra-class"><pre class="language-js"><code><span class="token keyword">var</span> <span class="token function-variable function">coinChange</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token parameter">coins<span class="token punctuation">,</span> amount</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>

    <span class="token keyword">const</span> memory <span class="token operator">=</span> <span class="token function">Array</span><span class="token punctuation">(</span>amount<span class="token punctuation">)</span><span class="token punctuation">.</span><span class="token function">fill</span><span class="token punctuation">(</span><span class="token operator">-</span><span class="token number">10</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

    <span class="token keyword">return</span> <span class="token function">calcCoinChange</span><span class="token punctuation">(</span>coins<span class="token punctuation">,</span> amount<span class="token punctuation">)</span>

    <span class="token keyword">function</span> <span class="token function">calcCoinChange</span><span class="token punctuation">(</span><span class="token parameter">coins<span class="token punctuation">,</span> amount</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">,</span> <span class="token string">'0'</span><span class="token punctuation">]</span><span class="token punctuation">.</span><span class="token function">includes</span><span class="token punctuation">(</span>amount<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">return</span> <span class="token number">0</span>
        <span class="token punctuation">}</span>
        
        <span class="token keyword">const</span> curIndex <span class="token operator">=</span> amount <span class="token operator">-</span> <span class="token number">1</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>memory<span class="token punctuation">[</span>curIndex<span class="token punctuation">]</span> <span class="token operator">!==</span> <span class="token operator">-</span><span class="token number">10</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>   
            <span class="token keyword">return</span> memory<span class="token punctuation">[</span>curIndex<span class="token punctuation">]</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">let</span> temp <span class="token operator">=</span> Number<span class="token punctuation">.</span><span class="token constant">MAX_VALUE</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">let</span> coin <span class="token keyword">of</span> coins<span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>amount <span class="token operator">-</span> coin <span class="token operator">&lt;</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token keyword">continue</span><span class="token punctuation">;</span>

            <span class="token keyword">const</span> result <span class="token operator">=</span> <span class="token function">calcCoinChange</span><span class="token punctuation">(</span>coins<span class="token punctuation">,</span> amount <span class="token operator">-</span> coin<span class="token punctuation">)</span><span class="token punctuation">;</span>

            <span class="token keyword">if</span> <span class="token punctuation">(</span>result <span class="token operator">===</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span> <span class="token keyword">continue</span><span class="token punctuation">;</span>
            temp <span class="token operator">=</span> Math<span class="token punctuation">.</span><span class="token function">min</span><span class="token punctuation">(</span>temp<span class="token punctuation">,</span> result <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        memory<span class="token punctuation">[</span>curIndex<span class="token punctuation">]</span> <span class="token operator">=</span> temp <span class="token operator">===</span> Number<span class="token punctuation">.</span><span class="token constant">MAX_VALUE</span> <span class="token operator">?</span> <span class="token operator">-</span><span class="token number">1</span> <span class="token operator">:</span> temp<span class="token punctuation">;</span>
        <span class="token keyword">return</span> memory<span class="token punctuation">[</span>curIndex<span class="token punctuation">]</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre></div><p>如图：</p> <p><img src="https://cdn.jsdelivr.net/gh/filess/img10@main/2021/05/31/1622445130675-454854f2-f963-4fb1-a143-6c9bd59f5281.png" alt=""></p> <p><strong>动态规划的写法</strong></p> <p>这种写法采用双重for循环加dp数组，也是自底向上的，动态规划是一种分阶段 求解 决策 的数学思想。下面这种写法的时间复杂度也是O(n)。</p> <div class="language-js extra-class"><pre class="language-js"><code><span class="token keyword">var</span> <span class="token function-variable function">coinChange</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token parameter">coins<span class="token punctuation">,</span> amount</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>

    <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">,</span> <span class="token string">'0'</span><span class="token punctuation">]</span><span class="token punctuation">.</span><span class="token function">includes</span><span class="token punctuation">(</span>amount<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token number">0</span>

    <span class="token keyword">const</span> dp <span class="token operator">=</span> <span class="token function">Array</span><span class="token punctuation">(</span>amount <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">.</span><span class="token function">fill</span><span class="token punctuation">(</span>amount <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span>
    dp<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">0</span>

    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">let</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> amount<span class="token punctuation">;</span> i <span class="token operator">++</span><span class="token punctuation">)</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">const</span> coin <span class="token keyword">of</span> coins<span class="token punctuation">)</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span>coin <span class="token operator">&lt;=</span> i<span class="token punctuation">)</span> <span class="token punctuation">{</span>
                dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> Math<span class="token punctuation">.</span><span class="token function">min</span><span class="token punctuation">(</span>dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span> dp<span class="token punctuation">[</span>i <span class="token operator">-</span> coin<span class="token punctuation">]</span> <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span>
            <span class="token punctuation">}</span>

    <span class="token keyword">return</span> dp<span class="token punctuation">[</span>amount<span class="token punctuation">]</span> <span class="token operator">&gt;</span> amount <span class="token operator">?</span> <span class="token operator">-</span><span class="token number">1</span> <span class="token operator">:</span> dp<span class="token punctuation">[</span>amount<span class="token punctuation">]</span>
<span class="token punctuation">}</span>
</code></pre></div><h2 id="另类题解"><a href="#另类题解" class="header-anchor">#</a> 另类题解</h2> <p>通过正则表达式和求斐波那契数列的方式来实现91题</p> <div class="language-js extra-class"><pre class="language-js"><code>
<span class="token comment">/**
 * @param {string} s
 * @return {number}
 */</span>
<span class="token keyword">var</span> <span class="token function-variable function">numDecodings</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token parameter">s</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>s<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token string">'0'</span><span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token regex"><span class="token regex-delimiter">/</span><span class="token regex-source language-regex">(30)|(40)|(50)|(60)|(70)|(80)|(90)|(00)</span><span class="token regex-delimiter">/</span></span><span class="token punctuation">.</span><span class="token function">test</span><span class="token punctuation">(</span>s<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
    list <span class="token operator">=</span> s<span class="token punctuation">.</span><span class="token function">match</span><span class="token punctuation">(</span><span class="token regex"><span class="token regex-delimiter">/</span><span class="token regex-source language-regex">(1|2)*(1[03456789])|(1|2)*(2[03456])|(1|2)+</span><span class="token regex-delimiter">/</span><span class="token regex-flags">g</span></span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>list<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">let</span> solve <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">,</span> minus <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">let</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span> i<span class="token operator">&lt;</span>list<span class="token punctuation">.</span>length<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            minus <span class="token operator">=</span> <span class="token regex"><span class="token regex-delimiter">/</span><span class="token regex-source language-regex">0$</span><span class="token regex-delimiter">/</span></span><span class="token punctuation">.</span><span class="token function">test</span><span class="token punctuation">(</span>list<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token operator">?</span> <span class="token number">2</span> <span class="token operator">:</span> <span class="token number">0</span><span class="token punctuation">;</span>
            solve <span class="token operator">*=</span> <span class="token function">fb</span><span class="token punctuation">(</span>list<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>length <span class="token operator">-</span> minus<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">return</span> solve
    <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token keyword">return</span> <span class="token number">1</span><span class="token punctuation">;</span>

    <span class="token keyword">function</span> <span class="token function">fb</span><span class="token punctuation">(</span><span class="token parameter">index</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>index <span class="token operator">&lt;=</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token number">1</span><span class="token punctuation">;</span>
        <span class="token keyword">var</span> num1 <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">,</span> num2 <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">,</span> ans <span class="token operator">=</span> <span class="token number">2</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">let</span> i<span class="token operator">=</span><span class="token number">2</span><span class="token punctuation">;</span> i<span class="token operator">&lt;</span>index<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            num1 <span class="token operator">=</span> num2<span class="token punctuation">;</span>
            num2 <span class="token operator">=</span> ans<span class="token punctuation">;</span>
            ans <span class="token operator">=</span> num1 <span class="token operator">+</span> num2<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">return</span> ans<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre></div></div></div> <div class="page-edit"><!----> <div class="tags"><a href="/tags/?tag=%E7%AE%97%E6%B3%95" title="标签">#算法</a></div> <div class="last-updated"><span class="prefix">上次更新时间:</span> <span class="time">10年18月2023日 01时57分53秒</span></div></div> <div class="page-nav-wapper"><div class="page-nav-centre-wrap"><a href="/pages/70741550255/" class="page-nav-centre page-nav-centre-prev"><div class="tooltip">第1题-两数之和</div></a> <a href="/pages/17845450445/" class="page-nav-centre page-nav-centre-next"><div class="tooltip">浅谈算法解析</div></a></div> <div class="page-nav"><p class="inner"><span class="prev">
        ←
        <a href="/pages/70741550255/" class="prev">第1题-两数之和</a></span> <span class="next"><a href="/pages/17845450445/"> 浅谈算法解析 </a>
        →
      </span></p></div></div></div> <div class="article-list"><div class="article-title"><a href="/archives/" class="iconfont icon-bi">最近更新</a></div> <div class="article-wrapper"><dl><dd>01</dd> <dt><a href="/pages/45343271027/"><div>01.数据结构导论一览.md</div></a> <span>10-16</span></dt></dl><dl><dd>02</dd> <dt><a href="/pages/38850370637/"><div>30.2023年06月04日.md</div></a> <span>06-04</span></dt></dl><dl><dd>03</dd> <dt><a href="/pages/74707370537/"><div>08.与测量相关.md</div></a> <span>05-06</span></dt></dl> <dl><dd></dd> <dt><a href="/archives/" class="more">更多文章&gt;</a></dt></dl></div></div> </main></div> <div class="footer"><!----> 
  Theme by
  <a href="https://github.com/xugaoyi/vuepress-theme-vdoing" target="_blank" title="本站主题">Vdoing</a> 
    | Copyright © 2017-2023
    <span class="link">aiyoudiao 码二</span> <span>备案号：</span> <a href="https://beian.miit.gov.cn/#/Integrated/index" target="_blank" title="备案号">鄂ICP备2022002654号-1</a></div> <div class="buttons"><div title="返回顶部" class="button blur go-to-top iconfont icon-fanhuidingbu" style="display:none;"></div> <div title="去评论" class="button blur go-to-comment iconfont icon-pinglun" style="display:none;"></div></div> <!----> <!----> <!----></div><div class="global-ui"><div></div><APlayer audio="" fixed="true" theme="#b7daff" loop="loop" order="list" preload="auto" volume="0.7" mutex="true" lrc-type="3" list-max-height="250" storage-name="vuepress-plugin-meting" id="aplayer-fixed"></APlayer><div id="VuepressPluginLive2d"></div></div></div>
    <script src="/assets/js/app.bd2fbc77.js" defer></script><script src="/assets/js/3.72c9c947.js" defer></script><script src="/assets/js/130.53e4f9c6.js" defer></script><script src="/assets/js/42.4251ca36.js" defer></script>
  </body>
</html>
